
package main.new_2024.month_02;


import main.dataStruct.TreeNode;

import java.util.*;

/**
 * @Description: todo 235. 二叉搜索树的最近公共祖先
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
 *
 * todo 2476. 二叉搜索树最近节点查询
 * 给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。
 * 请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
 * mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
 * maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。
 * 返回数组 answer 。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2024/2/27
 * @Param:
 * @return:
 **/
public class Solution0227 {

    //二叉搜索树最近节点查询:中序遍历，在二分查找
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        List<List<Integer>> result = new ArrayList<>();

        List<Integer> arr = new ArrayList<>();
        dfs(root, arr);
        //list 转 数组，方便二分
        int size = arr.size();
        int[] values = new int[size];
        for (int i = 0; i < size; i++) {
            values[i] = arr.get(i);
        }
        for (Integer target : queries){
            int search = search(values,target);
            int mx = search == size ? -1 : values[search];
            if (search == size || values[search] != target) { // a[j]>q, a[j-1]<q
                search--;
            }
            int mn = search < 0 ? -1 : values[search];
            result.add(Arrays.asList(mn, mx));
        }
        return result;
    }
    //中序遍历
    private void dfs(TreeNode root,List<Integer> arr){
        if (root == null){
            return;
        }
        dfs(root.left,arr);
        arr.add(root.val);
        dfs(root.right,arr);
    }
    //二分查找大于等于 targe 的下标
    private int search(int[] values,Integer target){
        int left = -1, right = values.length; // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            int mid = (left + right) >>> 1; // 比 /2 快
            if (values[mid] >= target) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        return right;
    }



    //二叉搜索树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int max = Math.max(p.val, q.val);
        int min = Math.min(p.val, q.val);
        if (root.val <= max && root.val >= min){
            return root;
        }else if (root.val > max){
            return lowestCommonAncestor(root.left,  p,  q);
        }else {
            return lowestCommonAncestor(root.right,  p,  q);
        }


    }

    public static void main(String[] args) {
        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(4);
        TreeNode t = new TreeNode(2,one,two);
        TreeNode q = new TreeNode(14);
        TreeNode w = new TreeNode(15,q,null);
        TreeNode e = new TreeNode(9);
        TreeNode r = new TreeNode(13,e,w);
        TreeNode root = new TreeNode(6,t,r);
        Solution0227 test = new Solution0227();
        List<Integer> queries = Arrays.asList(2,5,16);
        List<List<Integer>> lists = test.closestNodes(root, queries);
        System.out.println(lists);
    }

}

